package com.ufo.exercise;

import java.util.*;

/**
 * 据说古罗马时期，在罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲到一个洞中，
 * 他们宁愿死也不要被敌人抓到，于是约定了一个自杀方式，
 * 41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，
 * 然后再由下1个人重新报数，直到所有人都自杀身亡为止。
 * 但是Josephus和他的朋友并不想遵从，就开始想一开始要站在什么地方才能避免被处决
 *
 * 这就是约瑟夫问题：
 * N个身陷绝境的人未作成一圈（位置从0到N-1），并从第一个人开始报数，报到M的人会被杀死，直到最后一人留下来（或最后2个人）
 *
 * 编写一个函数接收N和M，打印出人们死亡的顺序
 */
public class Josephus {
    public static void main(String[] args) {

//        doIt(8,3);
//        doByArray(7,3);
        doByList(6,2);
    }


    //用环形链表
    static class Cycle<E>{
        E node;
        Cycle<E> next;

        public Cycle(boolean h) {
            if(h){
                next=this;
            }
        }
        public Cycle() {
        }
        public Cycle<E> removeNext(){
            this.next=getNext().getNext();
            return this;
        }
        public Cycle<E> add(E newOne) {
            if(this.node==null){
                this.node=newOne;
                return this;
            }
            Cycle<E> c=new Cycle<E>();
            c.setNode(newOne);
            c.next=this.next;
            this.next = c;
            return c;
        }
        public void setNode(E node) {
            this.node = node;
        }
        public Cycle<E> getNext(){
            return next;
        }
        public E getNode(){
            return node;
        }

        @Override
        public String toString() {
            StringBuilder s = new StringBuilder(node.toString());
            Cycle<E> loopNext=getNext();

            while(loopNext!=this){
//                System.out.println(loopNext.node);
                s.append(",").append(loopNext.getNode().toString());
                loopNext=loopNext.getNext();
            }
            return s.toString();
        }
    }
    public static void doIt(int n,int m){
        System.out.printf("N=%d,N=%d \n\r",n,m);
        if(n<=2){
            System.out.println("n <= 2 no need");
            return;
        }
        int[] result=new int[n];
        int idx=0;
        Cycle<Integer> head=new Cycle<Integer>(true);
        Cycle<Integer> cycle=head;
        for(int i=0;i<n;i++){
            cycle=cycle.add(i);
//            System.out.print(i);
        }
        System.out.println("初始状态：");
        System.out.println(head);
        Cycle<Integer> last=cycle;
        cycle=head;
        while(cycle!=cycle.getNext()){
            for(int i=1;i<m;i++){
                last=cycle;
                cycle=cycle.getNext();
            }
//            System.out.println(idx+++";"+cycle.getNode());
            result[idx++]=cycle.getNode();
            last.removeNext();
            cycle=last.getNext();
        }
        System.out.println("last one:"+last);
        result[idx]=last.getNode();
        System.out.println(Arrays.toString(result));
    }


    //用数组实现
    private static void doByArray(int n, int m) {
        System.out.printf("N=%d,N=%d \n\r",n,m);
        int[] arr=new int[n];
        for(int i=0;i<n;i++){
            arr[i]=i;
        }
        System.out.println(Arrays.toString(arr));
        int idx=0;
        for(int j=0;j<n;j++){
            idx=killNext(arr,idx,m);
        }
        System.out.println("last:"+(idx==0?n-1:idx-1));
    }
    private static int killNext(int[] arr,int i,int m){
        int j=i;
        for(int step=0;step<m;i=(++i)%arr.length){
            j=i;
            if(arr[i]!=-1){
                step++;
            }
        }
        arr[j]=-1;
//        System.out.println(j);
        return i;
    }


    private static void doByList(int n, int m) {
        List<Integer> list = new ArrayList<>();
        for(int i=0;i<n;i++){
            list.add(i);
        }
        int idx=0,size=n;
        while(size>1){
            idx=(idx+m-1)%size;
            list.remove(idx);
            size--;
        }
        System.out.println("list last:"+list.get(0));
    }

    //优化解法，来自Donald E. Knuth的《具体数学》，用递推公式f(N,M)=f((N-1,M)+M)%N
    //利用反推的思路

    //

}
